Multihop networks have been discussed as a key technology for future wireless communication techniques, due to inherent power/energy efficiency and ability to connect nodes out of range via intermediate relaying nodes at feasible power/energy levels. In a multihop network, nodes out of reach from each other may benefit from intermediately located nodes that can forward their messages from the source towards the destination. Traditionally, multihop networks have often been associated with so called ad hoc networks where nodes are mostly mobile and no central coordinating infrastructure exists. However, the idea of multihop networking can also be applied when nodes are fixed. In addition, one can also envision central coordination, in particular when nodes are fixed and channels are robust. One may also envision hybrid networks involving wired links in addition to wireless links in multihop networks.
Routing generally involves the basic tasks of determining suitable routing paths and transporting information through the network. The first of these tasks is normally referred to as route determination and the latter is often referred to as packet forwarding.
In source-routing, it is normally assumed that the source end node determines the entire route. The intermediate nodes then merely act as store-and-forward units, mindlessly forwarding the packet to the next node on the path to the destination node.
In hop-by-hop routing, each node basically determines and maintains a routing table with information, for each of a number of destinations, of a preferred next hop node. When a node receives a packet, it forwards the packet to the next hop node on the basis of information on the destination of the packet. The forwarding process continues from node to node until the packet reaches the destination.
The network nodes pass routing information and maintain their routing tables through the transfer of various routing information messages. The routing information naturally varies depending on the particular routing scheme used.
Hop-by-hop routing schemes are normally categorized into two main classes, namely link-state and distance-vector algorithms. Link-state algorithms generally flood routing information to all nodes (however solutions flooding only part of the network also exist), but each node then only sends information describing the state of its own links. Distance vector algorithms on the other hand are based on exchanging routing cost information only between neighboring nodes.
A classical approach is to span a so-called routing tree. FIG. 1A illustrates an example of such a routing tree, here rooted at a given destination node. In multihop networks, it is well known to calculate the routing tree based on a shortest path algorithm, implying that the determined shortest paths from the various nodes in the tree to the destination node are so-called “least cost paths”. Each link is then normally characterized by a delta cost, and each node is assigned an accumulated cost to reach the destination along the determined shortest path. In practice, the tree is continuously updated to manage mobility and changing link conditions.
The Bellman-Ford shortest path algorithm is a well known example of a shortest path algorithm (the Dijkstra algorithm is another example of classical routing algorithms). The Bellman-Ford algorithm has played a central role in wired networks such as the Internet, but also has an important function in wireless multihop networks. An advantage of the Bellman-Ford algorithm is that it can provide shortest path determination in a distributed and “uncoordinated” fashion. It also guarantees convergence within a finite time period based on the exchange of routing cost information between neighboring nodes.
For the Bellman Ford algorithm, the cost ci of a node νi for each destination d of a given set of destinations may thus be determined through the distributed Bellman Ford equation:
                                          C            i                          (              d              )                                =                                    min                              ∀                                  j                  ∈                                      N                    i                                                                        ⁢                          {                                                Δ                  ⁢                                                                          ⁢                                      C                    ij                                                  +                                  C                  j                                      (                    d                    )                                                              }                                      ,                            (        1        )            where νjεNi is the neighbor index of neighbor nodes belonging to node νi, Cj(d) is the cost for neighbor νj to reach destination d, and ΔCij is the cost to go from node νi to νj (i.e. the cost for a hop, or the link cost).
The number of iterations may be limited to an integer number, thereby upper limiting the number of hops, e.g. a maximum of two hops.
Anyway, when a particular node in the tree wants to send a packet in the subsequent packet forwarding process, the node is considered a source node, and the packet follows the determined routing path from the source to the destination, as illustrated in FIG. 1B. Different nodes may send packets to the same destination over time; hence different nodes will act as source nodes and send along their respective shortest path. In addition, as multiple destinations may exist, multiple trees may be generated, each rooted at a corresponding destination. When transmitting packets in the forwarding process, the nodes employ link control such as link adaptation and/or power control to provide efficient transmission.
As indicated above, a common objective of the routing schemes is normally to find a path that is optimal in some sense. For example, the expression “shortest path” normally corresponds to a minimum cost path, implying that the path or route is a path that offers the minimum cost with respect to some particular cost metric.
For instance, a common routing scheme in non-slotted channel access is to keep the transmit power constant for all hops, assuming that all hops experience different path losses, and selecting the path that offers the least accumulated transmit time (or delay).
In this context, an example of a suitable link metric is to use the estimated average link rate and define link cost as the inverse of the average link rate, i.e. ΔCij=1/ rij, assuming rate adaptation capabilities. This metric can be seen in two ways. First, for a fixed sized packet, it strives to offer minimum transmit time paths (assuming that the queuing delay in the network is negligible). However, in the context of a multihop scheme with a fixed sized data phase (with varying number of packets in the data phase depending on rate adaptation) it offers the least time resource utilization along a path. The average rate based link metric can be estimated by the classical Shannon capacity:
                                                        r              _                        ij                    =                      B            ·                          E              ⁡                              (                                                      log                    2                                    ⁡                                      (                                          1                      +                                                                                                    G                            ij                                                    ⁢                                                      P                            i                                                                                                    σ                          N                          2                                                                                      )                                                  )                                                    ,                            (        2        )            where B is the bandwidth (may be neglected if only one common bandwidth is used in the whole system), E{ . . . } is the expectation value, Pi is the transmit power of node νi (which may be fixed or determined by some other mechanism), σN2 is the noise level (at node νj). The term, σN2 could potentially also include average interference, then modeled as complex Gaussian noise, apart from receiver noise.
The same strategy may be used for a slotted channel access scheme, but then, instead of delay, the end-to-end time utilization for a message will be minimized. Even if this does not minimize the physical layer delay, since the delay will be the number of hops times the duration, it to some extent heuristically strives to enable packing of as many user-transmissions in a multihop network as possible.
Another common scheme in slotted channel access assumes that the rate per hop is the same (and hence the transmit time per packet or per bit) for all hops, and then the end-to-end (aggregate) power is minimized by power allocation over involved nodes. Alternatively, for identical rate over all hops, it may be sufficient to minimize the aggregate path loss.
An example of a possible metric in this context is to use the average link gain Gij and define link cost as the inverse of the average link gain [1], i.e. ΔCij=Gij−1. This metric provides large receiver SNR (Signal-to-Noise Ratio) values (with fixed power), and minimum power routes (with power control).
Determining the minimum power routes by using the Shannon capacity for a desired target link rate ri,j(Target) yields:
                              P          i                =                                            (                                                2                                                                                    r                        _                                                                    i                        ,                        j                                                                    (                        Target                        )                                                              B                                                  -                1                            )                        ⁢                                          σ                N                2                                            G                ij                                              ∝                      1                          G              ij                                                          (        3        )            
This generally corresponds to the case of the inverse path gain metric described above, if one assumes a single common target link rate over all links.
Reference [2] describes the use of link transmit power as a reasonable cost metric to minimize the cumulative transmit power used over an entire path. This is good for battery consumption and also reduces the interference level in the system, leaving space for new connections and thus allowing operation at higher network load.
It is possible to include interference in the metrics. Interference-based type of metrics include Least Interference Routing (LIR) [3], where the idea is to use a route that causes the least destructive interference, and Least Resistance Routing (LRR) [4], where the idea is to use the route encountering the least interference.
It is also possible to include traffic load in the metric. However, including such traffic aspects in the metric (e.g. incorporating aspects of traffic load and medium access rules) is not straightforward, as one then also needs to consider stability issues.
As indicated, traditional routing schemes typically ensure that the path taken minimizes accumulated link costs such as the accumulated transmit time (or delay), the accumulated or aggregate transmit power or the number of hops, allowing some link transmit parameter (e.g. link transmit power or link rate) to vary while keeping at least one other link transmit parameter constant (e.g. link rate or transmit power) over all links.